The planning of efficient delivery routes presents a variety of technical and logistical challenges. Routes may be fixed or variable. Postal mail delivery is an example of a fixed-route system, in which deliveries are made to the same addresses each day along a fixed route. Variable routes greatly complicate the route planning process. In many modern service businesses, delivery routes change in order to accommodate the changing needs of customers. In a parcel delivery service business, for example, delivery and pickup routes change frequently, as often as every day. Incremental improvements in efficiency within a variable-route system can yield great dividends in performance, profitability, and overall value.
A region to be served by a business may be divided into a collection of local service territories. Each service territory may include one or more hubs, from which a staff of service providers (drivers) in a fleet of vehicles may be dispatched to serve the territory. For many types of businesses, customer participation and daily demand are generally stochastic (random). A subset of customers with a repeating or daily need may sometimes be identified. Generally, however, the list of participating customer addresses will vary significantly on any given day. The types of services provided along the route may also vary significantly. For example, the service may include pickups as well as deliveries. Additionally, the service types often include specific pickup times or guaranteed delivery times.
The system constraints on a service business include the number and capacity of the vehicles in its fleet, the number of drivers, and the number of hours in a work day. The geography of the service territory also creates a unique set of constraints and challenges.
One approach to serving a territory, for example, may include dispatching vehicles from a central hub to a specific outlying area or cluster. The cluster method is not the most efficient approach for several reasons, including the fact that each vehicle is not being fully utilized between the hub and the outlying cluster. The inefficiencies of the cluster method increase as a service territory grows in size.
Another approach sometimes used for a service territory, for example, is to dispatch vehicles along major roads extending away from the hub, and along the same or different major roads when returning to the hub at the end of the work day. While this practice of dividing the territory into loop routes may meet customer demand, it is typically not the most optimal way to service an area. Like the cluster method, the loop method becomes less and less efficient as the service territory grows in size and the loops become narrower and longer.
Other approaches developed based on experience or tradition also become inefficient over time and result in significant losses in productivity when a service territory grows in size and complexity.
A variety of mathematical solutions have been developed in the field which attempt to generate solutions for the so-called Vehicle Routing Problem (VRP). These complex algorithms are generally impractical for daily route planning because they typically require far too much computation time. Add the variable of stochastic customer demand, and the mathematical algorithms grow more complex and require even longer computation times. Thus, there exists a need in the art for a route planning and optimization system capable of generating a solution quickly enough to dispatch a fleet of vehicles on a daily basis.
Driver familiarity with particular routes and customers is a goal for many service businesses. To date, however, the factor of driver familiarity has not been considered when planning daily routes that are optimized on a daily basis to meet a variable demand. Thus, there exists a need in the art for a route planning and optimization system that promotes driver familiarity while meeting the efficiency requirements of a stochastic demand.